package com.ztom.top100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 滑动窗口最大值
 * <p>
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 *
 * @author ZhangTao
 */
public class Code69MaxSlidingWindow {

    /**
     * 单调队列
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return null;
        }
        int[] res = new int[nums.length - k + 1];
        // 记录的是下标
        Deque<Integer> queue = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            queue.addLast(i);
            // 形成窗口
            if (i - k + 1 < 0) {
                continue;
            }
            // 过期
            if (queue.peekFirst() <= i - k) {
                queue.pollFirst();
            }
            res[index++] = nums[queue.peekFirst()];
        }
        return res;
    }

    /**
     * 分块
     * 从左到右, 依次分成每块 k 个并求每块的最大值
     * 从右到左, 依次分成每块 k 个并求每块的最大值
     * 求两者最大值
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return null;
        }
        int n = nums.length;
        int[] l = new int[n];
        int[] r = new int[n];
        for (int i = 0; i < n; i++) {
            if (i % k == 0) {
                l[i] = nums[i];
            } else {
                l[i] = Math.max(nums[i], l[i - 1]);
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (i ==  n - 1 || (i + 1) % k == 0) {
                r[i] = nums[i];
            } else {
                r[i] = Math.max(nums[i], r[i + 1]);
            }
        }

        int[] res = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            res[i] = Math.max(l[i], r[i + k - 1]);
        }
        return res;
    }
}
